Domination number and minimum dominating sets in pseudofractal scale-free web and Sierpi\'nski graph

摘要

The minimum dominating set (MDS) problem is a fundamental subject oftheoretical computer science, and has found vast applications in differentareas, including sensor networks, protein interaction networks, and structuralcontrollability. However, the determination of the size of a MDS and the numberof all MDSs in a general network is NP-hard, and it thus makes sense to seekparticular graphs for which the MDS problem can be solved analytically. In thispaper, we study the MDS problem in the pseudofractal scale-free web and theSierpi\'nski graph, which have the same number of vertices and edges. For bothnetworks, we determine explicitly the domination number, as well as the numberof distinct MDSs. We show that the pseudofractal scale-free web has a uniqueMDS, and its domination number is only half of that for the Sierpi\'nski graph,which has many MDSs. We argue that the scale-free topology is responsible forthe difference of the size and number of MDSs between the two studied graphs,which in turn indicates that power-law degree distribution plays an importantrole in the MDS problem and its applications in scale-free networks.